package HighMethod08;

/**
 * 最大字段和
 * 方法一;动态规划
 * 方法二：滑动窗口(穷举策略)
 */
public class MaxFieldSum {

    //含有数组的动态规划（其实数组没必要）
    public static int fieldSum(int[] x) {
        if(x.length ==0) return 0;

        if(x.length == 1) return x[0];

        int ans = 0;
        int []dp = new int[x.length];
        dp[0] = x[0];

        for (int i = 1; i < x.length; i++) {
            dp[i] = Math.max(dp[i], dp[i - 1] + x[i]);
//            ans = Math.max(ans, dp[i]);           //注意这里样写是不恰当的
        }

        for(int i=0;i<x.length;i++){
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    //动态规划（不断更新的当前数据，不用数组记录）
    public static int fieldSumOptimized(int[] x) {
        int thissum = 0;
        int maxsum = 0;
        for (int i = 0; i < x.length; i++) {
            thissum += x[i];
            if (thissum > maxsum) {     //当前数值比最大值大，更新最大值
                maxsum = thissum;
            }
            if (thissum < 0) {          //如果当前数值比最大值小，并且小于零了，如果是
//                if (i == 1) {
//                    maxsum = thissum;
//                }
                thissum = 0;
            }
        }
        return maxsum;
    }

    public static void main(String[] args) {

//        int[] X = {-2, 1, -3, 4, -1, 2, 1, -5, 4};      //最大字段和4,-1,2,1
        int[] X = { 4,-5};
        System.out.println("（优化前）最大字段和：" + fieldSum(X));
        System.out.println("（优化前）最大字段和：" + fieldSumOptimized(X));
    }
}
